// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 经典题目：斐波那契数列模型，路径问题，简单多状态

// 技巧：
// dp[] 表多开一个长度，处理数组越界及初始化复杂的问题
// dp[][] 表多开一行，多开一列
// 结合滚动数组优化 - 注意赋值顺序

// 总结经验:
// 动态规划题目如果定义完 dp[] 数组，发现 dp[i] 依赖前面的状态，也依赖后面的状态，那么想一想打家劫舍模型
// 如果觉得不像打家劫舍模型，那么搞一个数组预处理一下，搞成连续的数组，往打家劫舍模型上靠

// 例题 3：
// 给你一个整数数组 nums ，你可以对它进行一些操作。
// 次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
// 始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
//
//        示例 1：
//
//        输入：nums = [3,4,2]
//        输出：6
//        解释：
//        删除 4 获得 4 个点数，因此 3 也被删除。
//        之后，删除 2 获得 2 个点数。总共获得 6 个点数。
//        示例 2：
//
//        输入：nums = [2,2,3,3,3,4]
//        输出：9
//        解释：
//        删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
//        之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
//        总共获得 9 个点数。
//
//
//        提示：
//
//        1 <= nums.length <= 2 * 104
//        1 <= nums[i] <= 104

// 解题思路:
// 直接定义 dp[i] 为以 i 位置为结尾能获取的最大点数，但是发现 dp[i] 需要依赖前面的状态，也要依赖后面的状态
// 因此这样定义不对，想想打家劫舍模型
// 搞一个预处理数组 arr[],把 nums[] 中的数字放进 arr[] 里面: arr[nums[i]] += nums[i];
// 使用打家劫舍的思路，解决上述问题

public class DeleteAndEarn {
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        int[] arr = new int[10001];
        for(int i = 0; i < n; i++){
            arr[nums[i]] += nums[i];
        }

        int[] f = new int[10001];
        int[] g = new int[10001];

        f[0] = arr[0];
        g[0] = 0;

        for(int i = 1; i < 10001; i++){
            f[i] = g[i - 1] + arr[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }

        return Math.max(f[10000], g[10000]);
    }
}
